package leetcode.editor.cn;
//给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j !=
//k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 
//
// 你返回所有和为 0 且不重复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
//注意，输出的顺序和三元组的顺序并不重要。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,1]
//输出：[]
//解释：唯一可能的三元组和不为 0 。
// 
//
// 示例 3： 
//
// 
//输入：nums = [0,0,0]
//输出：[[0,0,0]]
//解释：唯一可能的三元组和为 0 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 3000 
// -10⁵ <= nums[i] <= 10⁵ 
// 
//
// Related Topics 数组 双指针 排序 👍 5836 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution15 {
     public List<List<Integer>> threeSum(int[] nums) {
             List<List<Integer>>  res = new ArrayList<>();
             Arrays.sort(nums);
             for(int f=0;f<nums.length;f++){
                 if(f > 0 && nums[f]  == nums[f-1]){
                     continue;
                 }
                 if(nums[f] > 0){
                     break;
                 }
                 int target = nums[f] * -1;
                 int t = nums.length-1;
                 for(int s=f+1;s<nums.length;s++){
                     if(s > f+1 && nums[s] == nums[s-1]){
                         continue;
                     }
                     while (s < t && nums[s] + nums[t] > target){
                         t--;
                     }
                     if(s >= t){
                         break;
                     }
                     if(nums[s] + nums[t] == target){
                         List<Integer> list = new ArrayList<>(3);
                         list.add(nums[f]);
                         list.add(nums[s]);
                         list.add(nums[t]);
                         res.add(list);
                     }
                 }
             }
             return res;
         }

        public List<List<Integer>> threeSum1(int[] nums) {
               List<List<Integer>>  res = new ArrayList<>();
               Arrays.sort(nums);
               int leftIndex = 0;
               int rightIndex = nums.length-1;
               while (leftIndex < nums.length-1 && nums[leftIndex] <= 0){
                   int lp = leftIndex;
                   int rp = rightIndex;
                   while (rp >= 0 && nums[rp] >= 0 ){
                       int min = nums[lp];
                       int max = nums[rp];
                       int target = (max + min) * -1;
                       if(target > nums[rp]){
                           break;
                       }
                       boolean flag = getTargetIndex(nums, target, lp+1, rp-1);
                       if(flag){
                           List<Integer> list = new ArrayList<>();
                           list.add(min);
                           list.add(max);
                           list.add(target);
                           res.add(list);
                           while (rp -1 >= 0 && nums[rp] == nums[rp-1]){
                               rp--;
                           }
                       }
                       rp--;
                   }
                   while (leftIndex+1 < nums.length-1 && nums[leftIndex] == nums[leftIndex+1]){
                       leftIndex ++;
                   }
                   leftIndex ++;
               }
               return res;
           }

           private boolean getTargetIndex(int[] nums,int target,int leftIndex,int rightIndex){
               if(leftIndex < 0 || rightIndex > nums.length-1 || target < nums[leftIndex] || target > nums[rightIndex]){
                   return false;
               }
               while (leftIndex <= rightIndex){
                   int midIdnex = (leftIndex + rightIndex)/2;
                   if(nums[midIdnex] == target){
                       return true;
                   }else if(nums[midIdnex] < target){
                       leftIndex = midIdnex + 1;
                   }else if(nums[midIdnex] > target){
                       rightIndex = midIdnex - 1;
                   }
               }
               return false;
           }
}
//leetcode submit region end(Prohibit modification and deletion)
